package com.leecode;

public class Leet53 {
	public static void main(String[] args) {
		System.out.println(new Leet53().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
	}
	public int maxSubArray(int[] nums) {
		int dp=nums[0];
		if(nums.length==1)return dp;
		int max=dp;

		for(int i=1;i<nums.length;i++){
			if(dp>0){
				dp+=nums[i];
			}else{
				dp=Math.max(dp,nums[i]);
			}

			if(dp>max)max=dp;
		}

		return max;
	}

	/**
	 * 100%,99%,类似fabonacci,
	 * 考点:以i结尾的最大连续串只有两种可能,表达式如下
	 * f(i)=Math.max(f(i-1)+i,i)
	 */
	public int maxSubArray2(int[] nums) {
		int pre=0;
		int max=nums[0];

		for(int a=0;a<nums.length;a++){
			pre=Math.max(pre+nums[a],nums[a]);
			if(pre>max)max=pre;
		}

		return max;
	}
}
